# -*- coding: utf-8 -*-
"""
    Time    : 2020/12/28 9:33 下午
    Author  : Thinkgamer
    File    : add03-数组中找出只出现一次的两个数.py
    Desc    : 58 商业化团队 一面题（1）
                给定一个数组，除了有两个数之外，其他的数都出现2两次，尝试使用 O(n)的思路找出这两个数
"""

arr = [1, 1, 3, 2, 4, 2, 4, 5, 6, 6, 7, 7]
def find_nums(arr):
	# 非 O(n) -> 其实也是 O(n)
	from collections import Counter
	_dict = Counter(arr)
	for k, v in _dict.items():
		if v != 2:
			print(k)
		

# O(n) 异或的方法：两个相同的数字异或为0，不同为1
# https://blog.csdn.net/weixin_43855930/article/details/106006623
# 两个相同的数字异或的结果是0，所以将数组里的数字进行异或，最后的结果就是两个出现一次的数字异或的结果，
# 然后找到该结果从右边起第一位是1的位置，根据该位置将数组的数字分为两组，该位置为1的是一组，为0的是一组，
# 出现一次的数字分别在这两组中，然后对这两组数字分别进行异或，最后的两个结果就是出现一次的数字。
def find_nums_v2(arr):
	if len(arr) < 2:
		return None
	number = 0
	count = 0
	for num in arr:
		number = number ^ num
	# 右移操作 2的幂相关
	while number % 2 == 0:
		number = number >> 1
		count += 1
	mask = 1 << count
	a, b = 0, 0
	for num in arr:
		if mask & num == 0:
			a = a ^ num
		else:
			b = b ^ num
	print(a, b)


find_nums_v2(arr)